//归并排序
#pragma once
//归并两个有序序列a[Low. .mid] 和a[mid+1. . high]
//为一个有序序列
template <typename E>
void Merge(E a[], E b[], int Low, int mid, int high)
{
    //归并序列a[Low. .mid] 和a[mid+1..high] 到b[Low. . high]
    int i = Low, j = mid + 1, k = Low;
    while (i <= mid && j <= high)
        b[k++] = (a[i] <= a[j]) ? a[i++] : a[j++];
    while (i <= mid)
        b[k++] = a[i++];
    while (j <= high)
        b[k++] = a[j++];
    //复制b[Low..high] 到a[Low. .high]
    for (int i = Low; i <= high; i++)
        a[i] = b[i];
}
//归并排序
template <typename E>
void MSort(E a[], E b[], int Low, int high)
{
    if (Low >= high)
        return;
    int mid = (Low + high) / 2;
    MSort(a, b, Low, mid);
    MSort(a, b, mid + 1, high);
    Merge(a, b, Low, mid, high);
}
//归并排序
template <typename E>
void MergeSort(E a[], int n)
{
    auto b = new E[n];
    MSort(a, b, 0, n - 1);
    delete[] b;
}